/*
EP3D is a real-time 3D planet engine , which in addition to providing 
substandard scene rendering and scene management, of course, it also 
provides some basic class libraries to build the entire virtual 
planet, or even the entire universe.

Copyright (C) 2010  Hongjiang Zhang	(zhjwyat@gmail.com)

This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef EP3D_ARRAY_H
#define EP3D_ARRAY_H
#include "EP3DBase.h"
#include "EP3DMemory.h"
#include "EP3DLogger.h"
#include "EP3DHeapSort.h"
#include "EP3DMath.h"

namespace EP3D
{
	template <class T>
	class Array
	{
	public:
		typedef T* Iterator;

		Array()
			:m_pkBuffer(NULL)
			,m_uiSize(0)
			,m_uiCapacity(0)
			,m_bIsSort(false)
		{
		}

		Array(const Array<T>& rhs)
			:m_pkBuffer(NULL)
			,m_uiSize(0)
			,m_uiCapacity(0)
			,m_bIsSort(false)
		{
			LogAssert(NULL == m_pkBuffer);

			m_uiCapacity = rhs.m_uiCapacity;
			m_uiSize = rhs.m_uiSize;
			if (m_uiCapacity > 0) {
				m_pkBuffer = EP3DNew T[m_uiCapacity];
				uint i;
				for (i = 0; i < m_uiSize; i++) {
					m_pkBuffer[i] = rhs.m_pkBuffer[i];
				}
			}
		}

		~Array()
		{
			if (m_pkBuffer) {
				EP3DDelete[] m_pkBuffer;
				m_pkBuffer = 0;
			}
		}

		Iterator Begin() const
		{
			return m_pkBuffer;
		}

		Iterator End() const
		{
			return m_pkBuffer + m_uiSize;
		}

		Iterator Find(const T& elem) const
		{
			uint uiIndex = 0;
			for (uiIndex = 0; uiIndex < m_uiSize; uiIndex++) {
				if (m_pkBuffer[uiIndex] == elem) {
					return &m_pkBuffer[uiIndex];
				}
			}
			return NULL;
		}

		uint FindIndex(const T& elem) const
		{
			uint uiIndex = 0;
			for (uiIndex = 0; uiIndex < GetSize(); uiIndex++) {
				if (m_pkBuffer[uiIndex] == elem) {
					return uiIndex;
				}
			}
			return MAX_UINT;
		}

		Iterator BinarySearch(const T& elem) const
		{
			uint num = GetSize();
			if (num > 0)
			{
				uint half;
				uint lo = 0;
				uint hi = num - 1;
				uint mid;
				while (lo <= hi) {
					if (0 != (half = num/2)) {
						mid = lo + ((num & 1) ? half : (half - 1));
						if (elem < m_pkBuffer[mid]) {
							hi = mid - 1;
							num = num & 1 ? half : half - 1;
						} 
						else if (m_pkBuffer[mid] < elem) {
							lo = mid + 1;
							num = half;
						} 
						else {
							return &m_pkBuffer[mid];
						}
					} 
					else if (0 != num) {
						if (elem != m_pkBuffer[lo]) {
							return NULL;
						}
						else {
							return  &m_pkBuffer[lo];
						}
					} 
					else {
						break;
					}
				}
			}
			return NULL;
		}

		uint BinarySearchIndex(const T& elem) const
		{
			uint num = GetSize();
			if (num > 0)
			{
				uint half;
				uint lo = 0;
				uint hi = num - 1;
				uint mid;
				while (lo <= hi) {
					if (0 != (half = num/2)) {
						mid = lo + ((num & 1) ? half : (half - 1));
						if (elem < m_pkBuffer[mid]) {
							hi = mid - 1;
							num = num & 1 ? half : half - 1;
						} 
						else if (m_pkBuffer[mid] < elem) {
							lo = mid + 1;
							num = half;
						} 
						else {
							return mid;
						}
					} 
					else if (0 != num) {
						if (elem != m_pkBuffer[lo]) {
							return MAX_UINT;
						}
						else {
							return lo;
						}
					} 
					else {
						break;
					}
				}
			}
			return MAX_UINT;
		}

		Iterator LinearSearch(const T& elem) const
		{
			for (Iterator iter = Begin(); iter != End(); ++iter) {
				if (elem == *iter) {
					return iter;
				}
			}

			return NULL;
		}

		uint LinearSearchIndex(const T& elem) const
		{
			for (unsigned int i = 0; i < m_uiSize; ++i) {
				if (elem == At(i)) {
					return i;
				}
			}

			return MAX_UINT;
		}

		void Add(const T& elem)
		{
			if (m_uiSize == m_uiCapacity) {
				Grow();
			}

			LogAssert(m_pkBuffer);
			m_pkBuffer[m_uiSize++] = elem;
		}

		void Pop()
		{
			LogAssert(m_uiSize > 0);
			LogAssert(m_uiCapacity >= m_uiSize);
			Erase(m_uiSize - 1);
		}

		void Append(const Array<T>& src)
		{
			uint uiIndex;
			uint uiSize = src.GetSize();
			for (uiIndex = 0; uiIndex < uiSize; uiIndex++) {
				Add(src[uiIndex]);
			}
		}

		void Reserve(uint uiSize)
		{
			LogAssert(uiSize > 0);

			if (uiSize > m_uiCapacity) {
				Reallocte(uiSize);
			}
		}

		void Resize(uint uiNewSize)
		{
			if (uiNewSize > m_uiSize) {
				Insert(m_uiSize, uiNewSize - m_uiSize, T());
			}
			else {
				Erase(uiNewSize, m_uiSize - uiNewSize);
			}
		}

		uint GetSize() const
		{
			return m_uiSize;
		}

		uint GetCapacity() const
		{
			return m_uiCapacity;
		}

		bool IsEmpty() const
		{
			return m_uiSize == 0;
		}

		T& Front() const
		{
			LogAssert(m_pkBuffer && m_uiSize > 0);
			return m_pkBuffer[0];
		}

		T& Back() const
		{
			LogAssert(m_pkBuffer && m_uiSize > 0);
			return m_pkBuffer[m_uiSize - 1];
		}

		void Insert(uint uiIndex, const T& elem)
		{
			LogAssert(uiIndex <= m_uiSize);
			if (uiIndex == m_uiSize) {
				Add(elem);
			}
			else {
				Move(uiIndex, uiIndex + 1);
				m_pkBuffer[uiIndex] = elem;
			}
		}

		void Insert(uint uiIndex, uint uiCount, const T& elem)
		{
			LogAssert(uiIndex <= m_uiSize);

			Move(uiIndex, uiIndex + uiCount);
			for (uint ui = uiIndex; uiIndex < uiIndex + uiCount; ui++) {
				At(uiIndex) = elem;
			}
		}

		Iterator Insert(Iterator it ,const T& elem)
		{
			LogAssert(m_pkBuffer && it >= m_pkBuffer && it < m_pkBuffer + m_uiSize);
			Insert(uint(it - m_pkBuffer), elem);
			return it;
		}

		Iterator Erase(Iterator it)
		{
			LogAssert(m_pkBuffer && it >= m_pkBuffer && it < m_pkBuffer + m_uiSize);
			Erase(uint(it - m_pkBuffer));
			return it;
		}

		Iterator Erase(Iterator first, Iterator second)
		{
			LogAssert(m_pkBuffer && first < second);
			LogAssert(first >= m_pkBuffer && first < m_pkBuffer + m_uiSize);
			LogAssert(second >= m_pkBuffer && second < m_pkBuffer + m_uiSize);

			Erase(
				uint(first - m_pkBuffer),
				uint(second - first));
			return first;
		}

		void Erase(uint uiIndex)
		{
			LogAssert(m_pkBuffer && uiIndex < m_uiSize);

			if (uiIndex == m_uiSize -1){
				Destroy(&m_pkBuffer[uiIndex]);
				m_uiSize--;
			}
			else {
				Move(uiIndex + 1, uiIndex);
			}
		}

		void Erase(uint uiIndex, uint uiCount)
		{
			LogAssert(m_pkBuffer && uiCount > 0 && uiIndex + uiCount < m_uiSize);

			if (uiIndex + uiCount == m_uiSize - 1) {
				for (uint i = uiIndex; i < m_uiSize; i++) {
					Destroy(&m_pkBuffer[i]);
					m_uiSize--;
				}
			}
			else {
				Move(uiIndex + uiCount, uiIndex); 
			}
		}

		void Clear()
		{
			uint uiIndex;
			for (uiIndex = 0; uiIndex < m_uiSize; uiIndex++) {
				Destroy(&m_pkBuffer[uiIndex]);
			}
			m_uiSize = 0;
		}

		T& GetAt(int i) const
		{
			LogAssert(i >=0 && i < (int)m_uiSize);
			LogAssert(m_pkBuffer);
			return m_pkBuffer[i];
		}

		T& operator [](uint uiIndex) const
		{
			LogAssert(m_pkBuffer && uiIndex < m_uiSize);
			return m_pkBuffer[uiIndex];
		}

		const Array<T>& operator =(const Array<T>& rhs)
		{
			if (this == &rhs) {
				return *this;
			}

			if (m_pkBuffer) {
				EP3DDelete[] m_pkBuffer;
				m_pkBuffer = 0;
				m_uiSize = 0;
				m_uiCapacity = 0;
				m_bIsSort = false;
			}

			if (m_uiCapacity < rhs.m_uiCapacity) {
				Reserve(rhs.m_uiCapacity);
			}

			Append(rhs);

			return *this;
		}

		T& At(uint uiIndex) const
		{
			return operator[](uiIndex);
		}

		void Sort()
		{
			if (!m_bIsSort && m_uiSize > 1) {
				HeapSort(m_pkBuffer, m_uiSize);
			}
			m_bIsSort = true;
		}

	private:
		void Grow()
		{
			uint uiGrowToSize = m_uiSize + 3 * m_uiSize / 8 + 32; 
			Reallocte(uiGrowToSize);
		}

		void Reallocte(uint uiNewSize)
		{
			T* pkOldData = m_pkBuffer;

			m_pkBuffer = EP3DNew T[uiNewSize];
			m_uiCapacity = uiNewSize;

			uint uiEnd = m_uiSize < uiNewSize ? m_uiSize : uiNewSize;

			for (uint i = 0; i < uiEnd; ++i) {
				Construct(&m_pkBuffer[i], pkOldData[i]);
			}

			for (uint j = 0; j < m_uiSize; ++j) {
				Destroy(&pkOldData[j]);
			}

			if (m_uiCapacity < m_uiSize) {
				m_uiSize = m_uiCapacity;
			}

			EP3DDelete [] pkOldData;
		}

		void Move(uint first, uint second)
		{
			LogAssert(m_pkBuffer && first < m_uiSize);

			if (first == second) {
				return;
			}

			uint uiNum = m_uiSize - first; 

			uint uiNeedSize =  second + uiNum;
			while (uiNeedSize > m_uiCapacity) {
				Grow();
			}

			if (first > second) {
				uint i;
				for (i = 0; i < uiNum; i++) {
					m_pkBuffer[second + i] = m_pkBuffer[first + i];
				}

				for (i = (first + i) - 1; i < m_uiSize; i++) {
					Destroy(&m_pkBuffer[i]);
				}
			}
			else {
				int i;
				for (i = uiNum - 1; i >= 0; --i) {
					m_pkBuffer[second + i] = m_pkBuffer[first + i];
				}

				for (i = int(first); i < int(second); i++) {
					Destroy(&m_pkBuffer[i]);
				}
			}

			m_uiSize = second + uiNum;
		}

		T* Construct(T* pMem, const T& value)
		{
			return new(pMem) T(value);
		}

		void Destroy(T* pkObject)
		{
			pkObject->~T();
		}

		T* m_pkBuffer;
		uint m_uiSize;
		uint m_uiCapacity;
		bool m_bIsSort;

	};
}
#endif